import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class UnionFindSet {
    int[] arr;

    public UnionFindSet(int space) {
        this.arr = new int[space];
        Arrays.fill(arr, -1);
    }

    void expand(int a) {
        int[] tmp = Arrays.copyOf(arr, a + 1);
        for (int i = arr.length; i < tmp.length; i++) {
            tmp[i] = -1;
        }
        arr = tmp;
    }

    //将b并入a中，其实并的是a，b的根，也即是a，b的最终指向
    public void union(int a, int b) {
        if (a >= arr.length || b >= arr.length) {
            expand(Math.max(a, b));
        }
        int indexA = find(a);
        int indexB = find(b);
        if (indexA == indexB) {
            return;
        }
        arr[indexA] = arr[indexA] + arr[indexB];
        arr[indexB] = indexA;//b指向a
    }

    //找到对应的根子集
    public int find(int index) {
        if (index >= arr.length) {
            expand(index);
        }
        if (index < 0) {
            throw new IndexOutOfBoundsException("下标不合法");
        }
        while (arr[index] >= 0) {//找到小于0的最终返回 最终父节点
            index = arr[index];//走到该下标的值指向的根
        }
        return index;
    }


    //求集合的个数
    public int unionCount() {
        int count = 0;
        for (int i : arr) {
            if (i < 0) {
                count++;
            }
        }
        return count;
    }

    public List<Integer> getRoot(){
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (i < 0) {
                list.add(i);
            }
        }
        return list;
    }
    public int[] getArr(){
        return arr;
    }

    public boolean isEmpty() {
        int size = 0;
        for (int j : arr) {
            if (j < 0) {
                size++;
            }
        }
        return size == arr.length;
    }
    //判断俩下表是否在同一个集合中
    public Boolean isUnion(int a, int b) {
        return find(a) == find(b);
    }

    //打印数组
    public void print() {

        System.out.print("index =  ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(i+"   ");
        }
        System.out.println();
        System.out.print("val   = ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "   ");
        }
    }

    //"a==b","b!=a"
    public boolean equationsPossible(String[] equations) {
        UnionFindSet set = new UnionFindSet(26);//26个字母
        //是=就加入 是!就判断
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) == '=') {//加入
                set.union(equations[i].charAt(0) - 'a', equations[i].charAt(3) - 'a');

            }
        }
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) == '!') {//加入
                if (set.isUnion(equations[i].charAt(0) - 'a', equations[i].charAt(3) - 'a')) {

                    return false;
                }}
        }
        return true;
    }

    public int findCircleNum(int[][] isConnected) {
        UnionFindSet set = new UnionFindSet(isConnected.length);
        for (int i = 0; i < isConnected.length; i++) {//遍历y
            for (int j = 0; j < isConnected[i].length; j++) {
                //遍历x
                if (isConnected[i][j] == 1) {
                    //说明在一个集合中 add
                    set.union(i, j);
                }
            }
        }
        return set.unionCount();//返回集合数目
    }
}